/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class KeysKeyboard {
	public int minSteps(int n) {
		if (n == 1) {
			return 0;
		} else {
			return help(n);
		}
	}

	private int help(int n) {
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				return minSteps(n / i) + i;
			}
		}
		return n;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		KeysKeyboard keyboard = new KeysKeyboard();
		for (int i = 1; i < 1000; i++) {
			System.out.println(keyboard.minSteps(i));
		}
	}

}
